【Java集合】ArrayList 和 LinkedList源码分析

ArrayList

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable

• ArrayList 是一个数组队列，相当于 动态数组。与Java中的数组相比，它的容量能动态增长
• 允许null
• ArrayList 实现了RandmoAccess接口，即提供了随机访问功能
• ArrayList中的操作不是线程安全的，通过Collections.synchronizedList(new ArrayList(…))包装，或者使用CopyOnWriteArrayList，Vector
• 初始容量DEFAULT_CAPACITY = 10
• 遍历ArrayList时，使用随机访问(即，通过索引序号访问)效率最高，而使用迭代器的效率最低！for循环遍历居中

数据结构

ArrayList包含了两个重要的对象：elementData 和 size。

transient Object[] elementData;
private int size;

• elementData 是”Object[]类型的数组”，它保存了添加到ArrayList中的元素。elementData是个动态数组，大小会根据ArrayList容量的增长而动态的增长，具体的增长方式，由ensureCapacity()函数控制。

// jdk1.8
int newCapacity = oldCapacity + (oldCapacity >> 1); // 默认1.5倍
    
// jdk1.6
int newCapacity = (oldCapacity * 3)/2 + 1;

• size 则是动态数组的实际大小。

源码

• add函数

public boolean add(E e) { // 添加元素
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

ensureCapacityInternal()确保elementData数组长度足够

private void ensureCapacityInternal(int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {	//是否为空数组
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }

    ensureExplicitCapacity(minCapacity);
}

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;

    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

grow函数对数组进行扩容

private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;	//扩容1.5倍
    int newCapacity = oldCapacity + (oldCapacity >> 1);	// 新容量小于参数指定容量，修改新容量
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)		// 新容量大于最大容量
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    elementData = Arrays.copyOf(elementData, newCapacity);	//拷贝
}

• remove(int index)

public E remove(int index) {
    rangeCheck(index);

    modCount++;
    E oldValue = elementData(index);

    int numMoved = size - index - 1;	// 需要移动的元素的个数
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);		//把指定下标到数组末尾的元素向前移动一个单位
    elementData[--size] = null; // clear to let GC do its work

    return oldValue;
}

• clear()

public void clear() {
    modCount++;

    // clear to let GC do its work
    for (int i = 0; i < size; i++)
        elementData[i] = null;

    size = 0;
}

• clone()

public Object clone() {
    try {
    ArrayList<?> v = (ArrayList<?>) super.clone();
    v.elementData = Arrays.copyOf(elementData, size);
    v.modCount = 0;
    return v;
    } catch (CloneNotSupportedException e) {
    // this shouldn't happen, since we are Cloneable
    throw new InternalError(e);
    }
}

• 序列化

//java.io.Serializable的写入函数
// 将ArrayList的“容量，所有的元素值”都写入到输出流中
private void writeObject(java.io.ObjectOutputStream s)
    throws java.io.IOException{
    // Write out element count, and any hidden stuff
    int expectedModCount = modCount;
    s.defaultWriteObject();
    // 写入“数组的容量”
    s.writeInt(elementData.length);

    // 写入“数组的每一个元素”
    for (int i=0; i<size; i++)
    s.writeObject(elementData[i]);

    if (modCount != expectedModCount) {
    throw new ConcurrentModificationException();
    }
}

// java.io.Serializable的读取函数：根据写入方式读出
// 先将ArrayList的“容量”读出，然后将“所有的元素值”读出
private void readObject(java.io.ObjectInputStream s)
    throws java.io.IOException, ClassNotFoundException {
    // Read in size, and any hidden stuff
    s.defaultReadObject();

    // 从输入流中读取ArrayList的“容量”
    int arrayLength = s.readInt();
    Object[] a = elementData = new Object[arrayLength];

    // 从输入流中将“所有的元素值”读出
    for (int i=0; i<size; i++)
    	a[i] = s.readObject();
}

fail-fast 机制

• Iterator在调用 next() 和 remove()时，都会执行 checkForComodification()。若 “modCount 不等于 expectedModCount”，则抛出ConcurrentModificationException异常，产生fail-fast事件。
• 无论是add()、remove()，还是clear()，只要涉及到修改集合中的元素个数时，都会改变modCount的值
• 通过CopyOnWriteArrayList解决线程安全：

private COWIterator(Object[] elements, int initialCursor) {
    cursor = initialCursor;
    // 新建COWIterator时，将集合中的元素保存到一个新的拷贝数组中。
    // 这样，当原始集合的数据改变，拷贝数据中的值也不会变化。
    snapshot = elements;
}

可以看出：

1. 和ArrayList继承于AbstractList不同，CopyOnWriteArrayList没有继承于AbstractList，它仅仅只是实现了List接口。

2. ArrayList的iterator()函数返回的Iterator是在AbstractList中实现的；而CopyOnWriteArrayList是自己实现Iterator。

3. ArrayList的Iterator实现类中调用next()时，会“调用checkForComodification()比较‘expectedModCount’和‘modCount’的大小”；但是，CopyOnWriteArrayList的Iterator实现类中，没有所谓的checkForComodification()，更不会抛出ConcurrentModificationException异常！

LinkedList

public class LinkedList<E>
	extends AbstractSequentialList<E>
	implements List<E>, Deque<E>, Cloneable, java.io.Serializable

• LinkedList 是一个继承于AbstractSequentialList的双向链表。它也可以被当作堆栈、队列或双端队列进行操作。
• LinkedList 实现 List 接口，能对它进行队列操作。
• LinkedList 实现 Deque 接口，即能将LinkedList当作双端队列使用。既然是双向链表, 顺序访问会非常高效，而随机访问效率比较低
• LinkedList支持序列化，能通过序列化去传输。
• LinkedList 实现了Cloneable接口，即覆盖了函数clone()，能克隆。
• 允许空元素，非同步，Collections.synchronizedList包装

数据结构

// jdk1.8
transient int size = 0;
transient Node<E> first;  // Pointer to first node
transient Node<E> last;  // Pointer to last node

class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;
	
	Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

// jdk 1.6
// 链表的表头，表头不包含任何数据。Entry是个链表类数据结构。
private transient Entry<E> header = new Entry<E>(null, null, null);

private static class Entry<E> {
	// 当前节点所包含的值
	E element;
	// 下一个节点
	Entry<E> next;
	// 上一个节点
	Entry<E> previous;
}

源码

• 双向链表和索引值的联系

实际原理非常简单，它就是通过一个计数索引值来实现的。

例如，当我们调用get(int location)时，首先会比较“location”和“双向链表长度的1/2”；若前者大，则从链表头开始往后查找，直到location位置；否则，从链表末尾开始先前查找，直到location位置

• add()

对于添加一个元素至链表中会调用add方法 -> linkLast方法。

public boolean add(E e) {
    // 添加到末尾
    linkLast(e);
    return true;
}
  
void linkLast(E e) {
    // 保存尾结点，l为final类型，不可更改
    final Node<E> l = last;
    // 新生成结点的前驱为l,后继为null
    final Node<E> newNode = new Node<>(l, e, null);
    // 重新赋值尾结点
    last = newNode;    
    if (l == null) // 尾结点为空
        first = newNode; // 赋值头结点
    else // 尾结点不为空
        l.next = newNode; // 尾结点的后继为新生成的结点
    // 大小加1    
    size++;
    // 结构性修改加1
    modCount++;
}

• addAll()

// 添加一个集合
public boolean addAll(int index, Collection<? extends E> c) {
    // 检查插入的的位置是否合法
    checkPositionIndex(index);
    // 将集合转化为数组
    Object[] a = c.toArray();
    // 保存集合大小
    int numNew = a.length;
    if (numNew == 0) // 集合为空，直接返回
    	return false;    
    Node<E> pred, succ; // 前驱，后继
    if (index == size) { // 如果插入位置为链表末尾，则后继为null，前驱为尾结点
        succ = null;
        pred = last;
    } else { // 插入位置为其他某个位置
        succ = node(index); // 寻找到该结点
        pred = succ.prev; // 保存该结点的前驱
    }

    for (Object o : a) { // 遍历数组
        @SuppressWarnings("unchecked") E e = (E) o; // 向下转型
        // 生成新结点
        Node<E> newNode = new Node<>(pred, e, null);
        if (pred == null) // 表示在第一个元素之前插入(索引为0的结点)
            first = newNode;
        else
            pred.next = newNode;
        pred = newNode;
    }

    if (succ == null) { // 表示在最后一个元素之后插入
        last = pred;
    } else {
        pred.next = succ;
        succ.prev = pred;
    }
    // 修改实际元素个数
    size += numNew;
    // 结构性修改加1
    modCount++;
    return true;
}

说明：参数中的index表示在索引下标为index的结点（实际上是第index + 1个结点）的前面插入。在addAll函数中，addAll函数中还会调用到node函数，get函数也会调用到node函数，此函数是根据索引下标找到该结点并返回，具体代码如下

Node<E> node(int index) {
    // 判断插入的位置在链表前半段或者是后半段
    if (index < (size >> 1)) { // 插入位置在前半段
        Node<E> x = first; 
        for (int i = 0; i < index; i++) // 从头结点开始正向遍历
            x = x.next;
        return x; // 返回该结点
    } else { // 插入位置在后半段
        Node<E> x = last; 
        for (int i = size - 1; i > index; i--) // 从尾结点开始反向遍历
            x = x.prev;
        return x; // 返回该结点
    }
}

• unlink(Node x)
  在调用remove移除结点时，会调用到unlink函数，unlink函数具体如下：

E unlink(Node<E> x) {
    // 保存结点的元素
    final E element = x.item;
    // 保存x的后继
    final Node<E> next = x.next;
    // 保存x的前驱
    final Node<E> prev = x.prev;
    
    if (prev == null) { // 前驱为空，表示删除的结点为头结点
        first = next; // 重新赋值头结点
    } else { // 删除的结点不为头结点
        prev.next = next; // 赋值前驱结点的后继
        x.prev = null; // 结点的前驱为空，切断结点的前驱指针
    }

    if (next == null) { // 后继为空，表示删除的结点为尾结点
        last = prev; // 重新赋值尾结点
    } else { // 删除的结点不为尾结点
        next.prev = prev; // 赋值后继结点的前驱
        x.next = null; // 结点的后继为空，切断结点的后继指针
    }

    x.item = null; // 结点元素赋值为空
    // 减少元素实际个数
    size--; 
    // 结构性修改加1
    modCount++;
    // 返回结点的旧元素
    return element;
}

• 序列化

// 将LinkedList的“容量，所有的元素值”都写入到输出流中
private void writeObject(java.io.ObjectOutputStream s)
      throws java.io.IOException {
    // Write out any hidden serialization magic
    s.defaultWriteObject();
    // Write out size
  	s.writeInt(size);
  
  	// Write out all elements in the proper order.
  	for (Node<E> x = first; x != null; x = x.next)
     	 s.writeObject(x.item);
}

// 先将LinkedList的“容量”读出，然后将“所有的元素值”读出
private void readObject(java.io.ObjectInputStream s)
      throws java.io.IOException, ClassNotFoundException {
    // Read in any hidden serialization magic
  	s.defaultReadObject();  
  	// Read in size
  	int size = s.readInt();
  
  	// Read in all elements in the proper order.
  	for (int i = 0; i < size; i++)
    	  linkLast((E)s.readObject());
}

总结

• ArrayList 是一个数组队列，相当于动态数组。它由数组实现，随机访问效率高，随机插入、随机删除效率低。 　　
• LinkedList 是一个双向链表。它也可以被当作堆栈、队列或双端队列进行操作。LinkedList随机访问效率低，但随机插入、随机删除效率低。

参考

http://www.cnblogs.com/skywang12345/p/3308556.html

http://www.cnblogs.com/skywang12345/p/3308807.html